As IC fabrication technology improves, manufacturers are able to integrate additional functionality onto a single silicon substrate. As the number of these functions increases, however, so does the complexity of the designs. Due to this complexity, computers are commonly utilized to increase the efficiency and the speed of the design process. As circuit designs grow in complexity, it is imperative to decrease the number of computer resources and hours spent on these designs. Especially, in the current climate of competition, it is of utmost importance that designers have access to design tools that can streamline and speed up the IC design process.
One design tool available for testing random logic utilizes automatic test pattern generation (ATPG). In ATPG, deterministic test patterns are pre-generated using a gate-level representation of the design netlist. The netlist defines the entire IC design including all components and interconnections. The pre-generated patterns are then stored in a memory and scanned into the circuit. After applying one or more functional clock cycles, the data is scanned out to capture the response data.
The development of ATPG algorithms has traditionally focused on testing combinational logic (i.e., logic with no internal memory states). While the problem of combinational ATPG is classified as NP complete (meaning that no complete solution can be reached in a reasonable amount of computer time/memory), various algorithms and heuristics have been developed that provide partial solutions. In general, the ATPG problem is kept combinational by placing specific requirements on any latches contained in the design. The prevailing practice is to require that the latches be connected into one or more shift registers that allow the latches to be both directly controlled and directly observed (such as techniques related to level sensitive scan design (LSSD) and other scan-based techniques).
Sequential ATPG, however, poses a significantly more difficult problem than combinational ATPG. In particular, the internal memory states of a logic design add another dimension to the ATPG problem search space. While combinational ATPG needs to consider a staggering number of logical possibilities, sequential ATPG has to consider an ordered sequence of logical possibilities. In fact, most LSSD and other scan-based techniques were developed in order to avoid having to solve sequential ATPG problems when testing large, complex logic designs.
Generally, the prior solutions assume a single, ungated clock. They are not suitable for use in designs with more than one clock, nor in designs where the clocks are gated (wherein a clock pulse at the design's input may or may not reach the latches being considered). The prior art also fails to address clock race conditions (wherein one latch supplies data to a second latch and both are controlled by the same clock) and poorly controlled clocking (wherein a latch's clocks are not directly controlled by the clock inputs to the design).
More specifically, one approach is to consider sequential circuits as if they were combinational. However, this is done only for purposes of identifying untestable (redundant) faults and this approach may be merely valid for simple clocking (i.e., single clock, no clock gating nor clock races). In another approach, sequential designs are treated as if they were combinational for purposes of test generation. However, this approach is applicable only to specific circuit topologies (e.g., the sequential design must be acyclic, the sequential depths of the logic paths must be balanced or internally balanced), and the clocking must be simple (i.e., single clock, no clock gating nor clock races).
A further approach discards latches (stripping them of their controllability and/or observability) that would interfere with maintaining a combinational approach to a somewhat sequential design. This approach also does not provide a solution for proceeding through a latch that has been clocked and would be unsuitable for situations where the same clock(s) are pulsed repeatedly or if there is a large sequential depth, in part, because all latches would quickly be discarded in such cases.